{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Search Tree to Greater Sum Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: bstToGst"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从二叉搜索树到更大和树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><span style=\"font-size:10.5pt\"><span style=\"font-family:Calibri\"><span style=\"font-size:10.5000pt\"><span style=\"font-family:宋体\"><font face=\"宋体\">给定一个二叉搜索树</font></span></span></span></span>&nbsp;<code>root</code>&nbsp;(BST)<span style=\"font-size:10.5pt\"><span style=\"font-family:Calibri\"><span style=\"font-size:10.5000pt\"><span style=\"font-family:宋体\"><font face=\"宋体\">，请将它的每个</font></span></span></span></span>节点<span style=\"font-size:10.5pt\"><span style=\"font-family:Calibri\"><span style=\"font-size:10.5000pt\"><span style=\"font-family:宋体\"><font face=\"宋体\">的值替换成树中大于或者等于该</font></span></span></span></span>节点<span style=\"font-size:10.5pt\"><span style=\"font-family:Calibri\"><span style=\"font-size:10.5000pt\"><span style=\"font-family:宋体\"><font face=\"宋体\">值的所有</font></span></span></span></span>节点<span style=\"font-size:10.5pt\"><span style=\"font-family:Calibri\"><span style=\"font-size:10.5000pt\"><span style=\"font-family:宋体\"><font face=\"宋体\">值之和。</font></span></span></span></span></p>\n",
    "\n",
    "<p>提醒一下， <em>二叉搜索树</em> 满足下列约束条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>节点的左子树仅包含键<strong> 小于 </strong>节点键的节点。</li>\n",
    "\t<li>节点的右子树仅包含键<strong> 大于</strong> 节点键的节点。</li>\n",
    "\t<li>左右子树也必须是二叉搜索树。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/05/03/tree.png\" style=\"height:273px; width:400px\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]\n",
    "<strong>输出：</strong>[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [0,null,1]\n",
    "<strong>输出：</strong>[1,null,1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中的节点数在&nbsp;<code>[1, 100]</code>&nbsp;范围内。</li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 100</code></li>\n",
    "\t<li>树中的所有值均 <strong>不重复</strong>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong>该题目与 538:&nbsp;<a href=\"https://leetcode-cn.com/problems/convert-bst-to-greater-tree/\">https://leetcode-cn.com/problems/convert-bst-to-greater-tree/&nbsp; </a>相同</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-search-tree-to-greater-sum-tree](https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-search-tree-to-greater-sum-tree](https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]', '[0,null,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildGst(self, node: TreeNode, from_parent: int) -> int:\n",
    "        if node is None:\n",
    "            return 0\n",
    "        \n",
    "        rst_sum = self.buildGst(node.right, from_parent)\n",
    "        lst_sum = self.buildGst(node.left, node.val + rst_sum + from_parent)\n",
    "        st_sum = lst_sum + node.val + rst_sum\n",
    "        node.val += from_parent + rst_sum\n",
    "        \n",
    "        return st_sum\n",
    "        \n",
    "\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "        self.buildGst(root, 0)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "        \"\"\"遍历，找到最小的那个值，然后再更新每个节点的值\n",
    "        \n",
    "        Arguments:\n",
    "            root {TreeNode} -- [description]\n",
    "        \n",
    "        Returns:\n",
    "            TreeNode -- [description]\n",
    "        \"\"\"\n",
    "        if not root:return None\n",
    "        if not root:return None\n",
    "        ret = []\n",
    "        def dfs(root,ret):\n",
    "            if root.left:\n",
    "                dfs(root.left,ret)\n",
    "            if root.right:\n",
    "                dfs(root.right,ret)\n",
    "            ret.append(root.val)\n",
    "\n",
    "        def add_val(root):\n",
    "            if root.left:\n",
    "                add_val(root.left)\n",
    "            if root.right:\n",
    "                add_val(root.right)\n",
    "            index_root = ret.index(root.val)\n",
    "            root.val = sum(ret[index_root:])\n",
    "        dfs(root,ret)\n",
    "        ret.sort()\n",
    "        add_val(root)\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# class Solution:\n",
    "#     def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "#         nums = []\n",
    "#         stack = []\n",
    "#         cur = root\n",
    "#         while stack or cur:\n",
    "#             while cur:\n",
    "#                 stack.append(cur)\n",
    "#                 cur = cur.left\n",
    "#             node = stack.pop()\n",
    "#             if node:\n",
    "#                 nums.append(node.val)\n",
    "#                 cur = node.right\n",
    "#         print(nums)\n",
    "#         i = 0\n",
    "#         cur = root\n",
    "#         stack = []\n",
    "#         while stack or cur:\n",
    "#             while cur:\n",
    "#                 stack.append(cur)\n",
    "#                 cur = cur.left\n",
    "#             node = stack.pop()\n",
    "#             if node:\n",
    "#                 node.val = sum(nums[i:])\n",
    "#                 i += 1\n",
    "#                 cur = node.right\n",
    "#         return root\n",
    "\n",
    "class Solution:\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "        cur = root\n",
    "        stack = []\n",
    "        val = 0\n",
    "        while stack or cur:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.right\n",
    "            node = stack.pop()\n",
    "            if node:\n",
    "                val += node.val\n",
    "                node.val = val\n",
    "                cur = node.left\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        prev = [0]\n",
    "        return self.bst_rec(root, prev)\n",
    "    def bst_rec(self, root, prev):\n",
    "        if not root:\n",
    "            return root \n",
    "        self.bst_rec(root.right, prev)\n",
    "        root.val += prev[0]\n",
    "        prev[0] = root.val\n",
    "        \n",
    "        self.bst_rec(root.left, prev)\n",
    "\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "        self.n = 0\n",
    "        \n",
    "        def helper(root):\n",
    "            if root:\n",
    "                helper(root.right)\n",
    "                root.val += self.n\n",
    "                self.n = root.val\n",
    "                helper(root.left)\n",
    "        helper(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "        self.preVal = -1\n",
    "\n",
    "        # self.deque = collections.deque()\n",
    "        #\n",
    "        # # 递归 从右子树开始的中序遍历，将修改后的节点值入栈\n",
    "        # def recur(node: TreeNode):\n",
    "        #     if not node: return\n",
    "        #     # 递归处理右子树\n",
    "        #     recur(node.right)\n",
    "        #     # 回溯到本层\n",
    "        #     if len(self.deque) > 0: node.val += self.deque.pop()\n",
    "        #     self.deque.append(node.val)  # 将累加结果入栈\n",
    "        #     # 递归处理左子树\n",
    "        #     recur(node.left)\n",
    "\n",
    "        # 递归 从右子树开始的中序遍历，维护一个pre变量\n",
    "        def recur(node: TreeNode):\n",
    "            if not node: return\n",
    "            # 递归处理右子树\n",
    "            recur(node.right)\n",
    "            # 回溯到本层\n",
    "            if self.preVal != -1: node.val += self.preVal\n",
    "            self.preVal = node.val  # 将累加结果入栈\n",
    "            # 递归处理左子树\n",
    "            recur(node.left)\n",
    "\n",
    "        recur(root)\n",
    "        return root\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root: TreeNode):\n",
    "            nonlocal total\n",
    "            if not root:\n",
    "                return \n",
    "            dfs(root.right)\n",
    "            total += root.val\n",
    "            root.val = total\n",
    "            dfs(root.left)\n",
    "        \n",
    "        total = 0\n",
    "        dfs(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "        total = 0\n",
    "        def dfs(root):\n",
    "            nonlocal total\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.right)\n",
    "            total += root.val\n",
    "            root.val = total\n",
    "            dfs(root.left)\n",
    "        \n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "        m = 0\n",
    "\n",
    "        def BFS(root):\n",
    "            nonlocal m\n",
    "            if not root:\n",
    "                return\n",
    "            BFS(root.right)\n",
    "            m += root.val\n",
    "            root.val = m\n",
    "            BFS(root.left)\n",
    "        \n",
    "        BFS(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "        # 右子树的和加上自身（大于+等于）\n",
    "        # 点到左右 后序遍历\n",
    "        \n",
    "        # dList = []\n",
    "        # def RSO(r):\n",
    "        #     if r.right:\n",
    "        #         RSO(r.right)\n",
    "        #     dList.append(r.val)\n",
    "        #     r.val = sum(dList)\n",
    "        #     if r.left:\n",
    "        #         RSO(r.left)\n",
    "        # RSO(root)\n",
    "        \n",
    "        vList = [0]\n",
    "        def RSO2(r):\n",
    "            if r.right:\n",
    "                RSO2(r.right)\n",
    "            print(r.val, end=' ')\n",
    "            r.val += vList[0]\n",
    "            vList[0] = r.val\n",
    "            if r.left:\n",
    "                RSO2(r.left)\n",
    "        RSO2(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.com/contest/weekly-contest-135/problems/binary-search-tree-to-greater-sum-tree/\n",
    "import os, sys, shutil, glob, re\n",
    "import time, calendar\n",
    "from datetime import datetime, timezone\n",
    "import hashlib, zipfile, zlib\n",
    "from math import *\n",
    "from operator import itemgetter\n",
    "from functools import wraps, cmp_to_key, reduce\n",
    "from itertools import count, combinations, permutations\n",
    "from collections import namedtuple, defaultdict, Counter\n",
    "from queue import Queue\n",
    "from bisect import bisect_left, bisect_right\n",
    "\n",
    "def refreshGlobals():\n",
    "  pass\n",
    "\n",
    "refreshGlobals()\n",
    "\n",
    "\n",
    "def getTreeNodeSum(node):\n",
    "  if not node:\n",
    "    return 0\n",
    "  return node.val + getTreeNodeSum(node.left) + getTreeNodeSum(node.right)\n",
    "\n",
    "def isLeaf(node):\n",
    "  return (not node.left) and (not node.right)\n",
    "\n",
    "\n",
    "# 递归修改树上节点 node.val → greaterSum\n",
    "def dfs(node, type, parNode):\n",
    "  if not node:\n",
    "    return\n",
    "\n",
    "  node.originalVal = node.val\n",
    "\n",
    "  if type == 'right':\n",
    "    node.val = parNode.val - parNode.originalVal - getTreeNodeSum(node.left)\n",
    "  else:\n",
    "    node.val = node.val + getTreeNodeSum(node.right) + parNode.val\n",
    "\n",
    "  dfs(node.left, 'left', node)\n",
    "  dfs(node.right, 'right', node)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "  def bstToGst(self, root):  # -> TreeNode\n",
    "    dfs(root, 'left', TreeNode(0))\n",
    "    return root\n",
    "\n",
    "if __name__ == '__main__' and ('SJDEAK' in os.environ):\n",
    "  from utils.tree import TreeNode, array2TreeNode\n",
    "\n",
    "  def test(*args):\n",
    "    print('输入数据: ', *args)\n",
    "    print('结果: ', Solution().bstToGst(*args), end='\\n-----\\n')\n",
    "\n",
    "\n",
    "  test()\n",
    "  test()\n",
    "else:\n",
    "  print = lambda *args, **kwargs: None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.sumVal = 0\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return\n",
    "        self.bstToGst(root.right)\n",
    "        self.sumVal += root.val\n",
    "        root.val = self.sumVal\n",
    "        self.bstToGst(root.left)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "        self.sum = 0\n",
    "        def middle_travese(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            middle_travese(root.right)\n",
    "            root.val += self.sum \n",
    "            self.sum = root.val\n",
    "            middle_travese(root.left)\n",
    "        middle_travese(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # cur = 0\n",
    "    def __init__(self):\n",
    "        self.cur = 0  #保存前一个节点的值（更新后）\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "        # nonlocal cur\n",
    "        if not root:\n",
    "            return\n",
    "        self.bstToGst(root.right) #右\n",
    "        root.val = self.cur+root.val #中，当前节点等于前一个节点+当前节点值\n",
    "        self.cur = root.val #更新前一个节点值\n",
    "        self.bstToGst(root.left) #左\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "        self.sum_num = 0\n",
    "        def Traverse(root):\n",
    "            if not root:\n",
    "                return\n",
    "            Traverse(root.right)\n",
    "            self.sum_num += root.val\n",
    "            root.val = self.sum_num\n",
    "            Traverse(root.left)\n",
    "        Traverse(root)\n",
    "        return root\n",
    "    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "        self.sum_num = 0\n",
    "        def Traverse(root):\n",
    "            if not root:\n",
    "                return\n",
    "            Traverse(root.right)\n",
    "            self.sum_num += root.val\n",
    "            root.val = self.sum_num\n",
    "            Traverse(root.left)\n",
    "        Traverse(root)\n",
    "        return root\n",
    "    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "        res = list()\n",
    "        def inorder(root, res):\n",
    "            if not root: return\n",
    "\n",
    "            inorder(root.left, res)\n",
    "            res.append(root.val)\n",
    "            inorder(root.right, res)\n",
    "\n",
    "        def inorder_update(root, val_lst):\n",
    "            if not root: return\n",
    "            \n",
    "            inorder_update(root.left, val_lst)\n",
    "            root.val = val_lst.pop(0)\n",
    "            inorder_update(root.right, val_lst)\n",
    "        inorder(root, res)\n",
    "\n",
    "        val_lst = list()\n",
    "        for val in range(len(res)):\n",
    "            tmp = res[val]\n",
    "            for node in range(val + 1, len(res)):\n",
    "                if res[val] <= res[node]:\n",
    "                    tmp += res[node]\n",
    "                    print(res[node],tmp)\n",
    "                    \n",
    "            val_lst.append(tmp)\n",
    "        print(res)\n",
    "        print(val_lst)\n",
    "        inorder_update(root, val_lst)\n",
    "        \n",
    "        \n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    sum = 0\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "        self.traverse(root)\n",
    "        return root\n",
    "    \n",
    "    def traverse(self, root):\n",
    "        if root==None:\n",
    "            return\n",
    "        \n",
    "        self.traverse(root.right)\n",
    "        self.sum += root.val\n",
    "        root.val = self.sum\n",
    "        self.traverse(root.left)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "        self.sum = 0\n",
    "        self.traverse(root)\n",
    "        return root\n",
    "    def traverse(self, root):\n",
    "        if root is None:\n",
    "            return None\n",
    "        \n",
    "        self.traverse(root.right)\n",
    "        self.sum += root.val\n",
    "        root.val = self.sum\n",
    "        self.traverse(root.left)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstToGst(self, root: TreeNode) -> TreeNode:\n",
    "        val_sum = [0]\n",
    "        \n",
    "        def tra(root):\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            tra(root.right)\n",
    "            val_sum[0] += root.val\n",
    "            root.val = val_sum[0]\n",
    "            tra(root.left)\n",
    "        \n",
    "        tra(root)\n",
    "        return root"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
